1. Field of the Invention
The present Application relates to data encoding systems and methods. More particularly, the present Application relates to variable length encoding systems.
2. Description of Related Art
The well-known Advanced Audio Coding (“AAC”) method is used in various applications implementing audio codecs, including wireless, CATV, digital broadcast and Internet arenas. AAC generally provides high efficiency audio encoding. AAC decoder technology relies on Huffman decoding of variable length symbols. AAC schemes often use 11 Huffman tables as specified by the MPEG-2 and MPEG-4 audio standards. As commonly implemented, Huffman decoding resolves two bits at a time and, as a result, suffers from high computational complexity. Resolving more than 2 bits at a time is not contemplated because of the associated exponential increase in Huffman tables and consequent increased memory requirements.
Processing efficiency in systems implementing Huffman coding is generally achieved by increasing Huffman table sizes. Efficiency increases because increased table sizes permits a larger number of bits to be decoded for each lookup. Therefore, the index to a Huffman table should have a bit field of length equal to the maximum size of a field to be decoded. Thus, for example, a field of maximum length equal to 5 bits would be most efficiently decoded using a Huffman table having a size of Stable=25=32 elements. In another example, a field size of 16 bits requires a Huffman table size, Stable=216=65,536. It can be appreciated, however, that efficiency is limited by the amount of storage available to maintain large Huffman tables. In many systems, tradeoff between efficiency and table size is manifested as a compromise between performance and cost of storage.
Large Huffman tables are often desirable in schemes that encode multiple symbols per codeword. In MP3 and AAC Audio coding specification, each variable length bit field can represent values for 1, 2 or 4 consecutive samples. For convenience, such groups of symbols will be referred to as 2-tuple, 4-tuple and n-tuple, where “n” signifies the number of symbols encoded. A MP3 or AAC audio encoder may choose to adaptively use a Huffman Table that is appropriate for 2-tuple or 4-tuple fields. The choice of which table is chosen is sent as a side information that is embedded in the MP3/AAC bit-stream.
Finally, the individual sample values in a 2-tuple or a 4-tuple may be signed values. When signed values are to be encoded, the magnitude of these 2-tuple/4-tuple fields are first encoded using the appropriate Huffman Tables followed by their sign-bits.